package com.adee.algorithm.structure.s01_stack;

import org.junit.Test;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

// 最佳实践：作为栈工具，首选 Deque<Integer> s = new LinkedList<>();
public class Test001_Stask {

    // LinkedList，是一个双端队列Deque
    @Test
    public void test01() {
        // LinkedList 是 Java 集合框架中的一个重要类，它实现了 List 和 Deque 接口，基于双向链表的数据结构实现。下面从基本概念、常用方法、优缺点、使用场景等方面详细介绍 LinkedList。
        //基本概念
        //LinkedList 是一个双向链表，每个节点包含三个部分：数据元素、指向前一个节点的引用和指向后一个节点的引用。这种结构使得 LinkedList 在插入和删除操作上具有较高的效率，尤其是在链表的头部和尾部进行操作。
        //常用方法
        //1. 添加元素
        //add(E e)：将指定元素添加到列表的末尾。
        //add(int index, E element)：将指定元素插入到列表的指定位置。
        //addFirst(E e)：将指定元素插入到列表的开头。
        //addLast(E e)：将指定元素添加到列表的末尾，等同于 add(E e)。
        //2. 删除元素
        //remove()：移除并返回列表的第一个元素。
        //remove(int index)：移除列表中指定位置的元素。
        //removeFirst()：移除并返回列表的第一个元素。
        //removeLast()：移除并返回列表的最后一个元素。
        //3. 获取元素
        //get(int index)：返回列表中指定位置的元素。
        //getFirst()：返回列表的第一个元素。
        //getLast()：返回列表的最后一个元素。
        //4. 其他常用方法
        //size()：返回列表中的元素个数。
        //isEmpty()：判断列表是否为空。
        //contains(Object o)：判断列表中是否包含指定元素。

        // 创建一个 LinkedList 对象
        LinkedList<String> linkedList = new LinkedList<>();

        // 添加元素
        linkedList.add("Apple");  // 内部调用addLast，尾插
        linkedList.add("Banana");
        linkedList.addFirst("Cherry");
        linkedList.addLast("Date");

        // 输出列表元素，按从头到尾的顺序
        System.out.println("LinkedList: " + linkedList);

        // 获取指定位置的元素
        String element = linkedList.get(1);
        System.out.println("Element at index 1: " + element);

        // 删除元素
        linkedList.remove(2);
        System.out.println("After removing element at index 2: " + linkedList);

        // 检查列表是否包含指定元素
        boolean contains = linkedList.contains("Banana");
        System.out.println("LinkedList contains 'Banana': " + contains);

        // 获取列表的大小
        int size = linkedList.size();
        System.out.println("Size of LinkedList: " + size);
    }

    // java中可以作为栈使用的工具有几种：
    //      Stack（继承Vector，线程安全，使用synchronized，低效）
    //      LinkedList（双端链表，增删高效、查询低效，储存指针，相比数组耗内存）
    //

    // 1.使用 java.util.Stack 类
    //java.util.Stack 类是 Java 集合框架中提供的一个栈实现，它继承自 Vector 类，是线程安全的。
    //常用方法
    //push(E item)：将元素压入栈顶。
    //pop()：移除并返回栈顶元素，如果栈为空则抛出 EmptyStackException 异常。
    //peek()：返回栈顶元素，但不移除它，如果栈为空则抛出 EmptyStackException 异常。
    //empty()：判断栈是否为空。
    //search(Object o)：返回对象在栈中的位置，以 1 为基数，如果对象不在栈中则返回 -1。
    @Test
    public void test02() {
        Stack<Integer> s = new Stack<>();
        s.push(1);  // 入栈
        s.push(2);  // 入栈
        s.push(3);  // 入栈
        System.out.println(s.pop());  // 出栈
        System.out.println(s.peek());  // 获取栈顶元素
        System.out.println(s.pop());
        System.out.println(s.peek());
        System.out.println(s.pop());
        if (!s.empty()) {
            System.out.println(s.pop());  // 栈为空时，抛出异常 java.util.EmptyStackException
        }
    }

    // LinkedList作为栈使用
    @Test
    public void test03() {
        Deque<Integer> s = new LinkedList<>();
        s.push(1);
        s.push(2);
        s.push(3);
        System.out.println(s.pop());
        System.out.println(s.peek());
        System.out.println(s.pop());
        System.out.println(s.peek());
        System.out.println(s.pop());
    }

}
